Monoid 的同態 (homomorphisms)

直接看例子吧！

"foo".length + "bar".length == ("foo" + "bar").length

左邊是整數的 Monoid，右邊是字串的 Monoid，而 length 這個 function 保留了 Monoid 結構，這個 function 就稱為 monoid homomorphisms，一個 monoid homomorphisms f 在 M 和 N 這 2 個 Monoid 之間會遵守以下定律：

M.combine(f(x), f(y)) == f(N.combine(x, y))

可摺疊的資料結構

昨天 有提到 Monoid 跟 List 有著相當緊密的關係，其實不管是 List、LazyList 或其它有用到 foldLeft 或 foldRight 的地方，我們並不在意摺的東西是什麼，配合 Monoid 的話，其實我們可以把摺的動作抽象成 Foldable 這個資料結構：

trait Foldable[F[_]]:

  extension[A] (as: F[A])
    def foldRight[B](acc: B)(f: (A, B) => B): B

    def foldLeft[B](acc: B)(f: (B, A) => B): B

    def foldMap[B](f: A => B)(using mb: Monoid[B]): B =
      as.foldRight(mb.empty)((a, b) => mb.combine(f(a), b))

    def combineAll(using ma: Monoid[A]): A =
      as.foldLeft(ma.empty)(ma.combine)

    def toList: List[A] =
      as.foldRight(List.empty[A])(_ :: _)

Functor[F[_]] 型態建構子的相關說明請參考 Day 19；

extension 的說明請參考 Day 14；

Scala 3 加入了 contextual abstraction，概念很像 Scala 2 的 implicits，主要是在 function 中可以加入 using 關鍵字，把它變成具有上下文關係的參數 (context parameters)，在呼叫該 function 時，只要在程式中 given 一下，就能在不用給 using 參數的情況下使用它。

scala> trait Ord[T]:
|   def compare(x: T, y: T): Int
|   extension (x: T)
|     def < (y: T) = compare(x, y) < 0
|     def > (y: T) = compare(x, y) > 0
|
| given Ord[Int] with
|   def compare(x: Int, y: Int) =
|     if x < y then -1 else if x > y then +1 else 0

scala> def max[T](x: T, y: T)(using ord: Ord[T]): T =
|   if ord.compare(x, y) < 0 then y else x

scala> val r = max(2, 3) // 調用 max 時並沒有給 ord 這個參數
val r: Int = 3

然後我們嘗試用 List 來實作 Foldable 吧！

object Foldable:

  given Foldable[List] with
    extension[A] (as: List[A])
      def foldRight[B](acc: B)(f: (A, B) => B): B =
        as.foldRight(acc)(f)

      def foldLeft[B](acc: B)(f: (B, A) => B): B =
        as.foldLeft(acc)(f)

配合 Day 22 實作的 stringMonoid，我們就可以用 Foldable 做 foldMap。

scala> import Foldable.given
scala> given Monoid[String] = stringMonoid

scala> val foldedString = List(1, 2, 3).foldMap(_.toString)
val foldedString: String = 123

Monoids 的組合性

Monoid 最強大的地方在於它的組合性，如果 A 和 B 都是 Monoid，配對後的 tuple 型態 (A, B) 也是 Monoid。

Exercise D24-1

用以上的概念實作 productMonoid function 吧！

def productMonoid[A, B](ma: Monoid[A], mb: Monoid[B]): Monoid[(A, B)]

組裝更複雜的 Monoids

某些資料型態的 Monoid 能包含其他的 Monoid 進去，舉例來說，我們這裡有一個能合併 map 的 Monoid，

  def mapMergeMonoid[K, V](mv: Monoid[V]): Monoid[Map[K, V]] = new:
    def combine(a: Map[K, V], b: Map[K, V]) =
      (a.keySet ++ b.keySet).foldLeft(empty): (acc, k) =>
        acc.updated(k, mv.combine(a.getOrElse(k, mv.empty),
          b.getOrElse(k, mv.empty)))

    val empty = Map.empty

然後來組裝成這種類型的 Monoid，

scala> val M: Monoid[Map[String, Map[String, Int]]] = mapMergeMonoid(mapMergeMonoid(intAddition))
val m: Monoid[Map[String, Map[String, Int]]] = anon$1@1f40bb80

最後我就可以用 Monoid 來合併 2 個 Map[String, Map[String, Int]]，不需要額外的程式執行合併動作。

scala> val m1 = Map("o1" -> Map("i1" -> 1, "i2" -> 2))
val m1: Map[String, Map[String, Int]] = Map(o1 -> Map(i1 -> 1, i2 -> 2))

scala> val m2 = Map("o1" -> Map("i2" -> 3))
val m2: Map[String, Map[String, Int]] = Map(o1 -> Map(i2 -> 3))

scala> val m3 = M.combine(m1, m2)
val m3: Map[String, Map[String, Int]] = Map(o1 -> Map(i1 -> 1, i2 -> 5))

用組合式的 Monoid 來融合迭代

最後，我們組合多個 Monoid 為一個，這意味著我們在摺疊資料時可以同時執行多個計算，舉例來說，我們用 Monoid 在一個迭代同時計算 List 的長度和加總，最後在算出平均值：

scala> val m = productMonoid(intAddition, intAddition)
val m: Monoid[(Int, Int)] = anon$1@bd8f424

scala> val p = List(1,2,3,4).foldMap(a => (1, a))(using m)
val p: (Int, Int) = (4,10)

scala> val mean = p._2 / p._1.toDouble
val mean: Double = 2.5

總結

這 3 天介紹了第一個純粹的代數資料結構 Monoid，還有可摺疊的資料結構 Foldable，還有許多 Monoid 用在寫程式上的特性，透過 Monoid 的組合性，我們可以寫出許多有用的 helper 程式來幫助我們操作資料並簡化某些計算。

Day 24 - Exercise answer